#include "pch.h"
#include "ThreadBinTree.h"

void InitBinTree(BinTree *t, ElemType ref)
{
	t->root = NULL;
	t->refvalue = ref;
}

void CreateBinTree(BinTree *bt, BinTreeNode *&t, char *&str) {
	if (*str == bt->refvalue)
		t == NULL;
	else {
		t = (BinTreeNode*)malloc(sizeof(BinTreeNode));
		assert(t != NULL);
		t->data = *str;
		CreateBinTree(bt, t->leftChild, ++str);
		CreateBinTree(bt, t->rightChild, ++str);
	}
}
void CreateBinTree(BinTree *bt, char *str) {
	CreateBinTree(bt, bt->root, str);
}


void CreateInThread(BinTreeNode *&t, BinTreeNode *&pre) {
	if (t == NULL)
		return;
	CreateInThread(t->leftChild, pre);
	if (t->leftChild == NULL) {
		t->leftChild = pre;
		t->ltag = THREAD;
	}
	if (pre != NULL && pre->rightChild == NULL)
	{
		pre->rtag = THREAD;
		pre->rightChild = t;
	}
	pre = t;
	CreateInThread(t->rightChild, pre);
}
void CreateInThread(BinTree *t) {
	BinTreeNode *pre = NULL;
	CreateInThread(t->root, pre);
	pre->rightChild = NULL;
	pre->rtag = THREAD;
}


BinTreeNode* First(BinTreeNode *t) {
	if (t == NULL)
		return NULL;

	BinTreeNode *p = t;
	while (p->ltag == LINK)
		p = p->leftChild;
	return p;
}
BinTreeNode* First(BinTree *t)
{
	return First(t->root);
}

BinTreeNode* Last(BinTreeNode *t) {
	if (t == NULL)
		return NULL;

	BinTreeNode *p = t;
	while (p->rtag == LINK) p = p->rightChild;
	return p;
}
BinTreeNode* Last(BinTree *t)
{
	return Last(t->root);
}

BinTreeNode* Next(BinTreeNode *t, BinTreeNode *cur) {
	if (t == NULL||cur==NULL)
		return NULL;

	if (cur->rtag == THREAD)
		return cur->rightChild;
	return First(cur->rightChild);
}
BinTreeNode* Next(BinTree *t,BinTreeNode *cur)
{
	return Next(t->root,cur);
}


BinTreeNode* Prio(BinTreeNode *t, BinTreeNode *cur) {
	if (t == NULL || cur == NULL)
		return NULL;

	if (cur->ltag == THREAD)
		return cur->leftChild;
	return Last(cur->leftChild);
}
BinTreeNode* Prio(BinTree *t, BinTreeNode *cur)
{
	return Prio(t->root, cur);
}

void InOrder(BinTreeNode *t)
{
	BinTreeNode *p=NULL;
	for (p = First(p); p != NULL; p = Next(t, p))
		printf("%c", p->data);
	printf("\n");
}
void InOrder(BinTree *t) {
	InOrder(t->root);
}


BinTreeNode* Search(BinTreeNode *t, ElemType key)
{
	if (t == NULL)
		return NULL;
	if (t->data == key)
		return t;
	BinTreeNode *p;
	for (p = First(t); p != NULL; p = Next(t, p))
	{
		if (p->data == key)
			return p;
	}
	return NULL;
}
BinTreeNode* Search(BinTree *t, ElemType key)
{
	return Search(t->root, key);
}


BinTreeNode* Parent(BinTreeNode *t, BinTreeNode *cur)
{
	if (t == NULL || cur == NULL)
		return NULL;
	if (t == cur)
		return NULL;

	BinTreeNode *p;
	if (cur->ltag == THREAD)
	{
		p = cur->leftChild;
		if (p->rightChild == cur)
			return p;
	}
	if (cur->rtag == THREAD)
	{
		p = cur->rightChild;
		if (p->leftChild == cur)
			return p;
	}

	p = First(cur->leftChild);
	p = p->leftChild;
	if (p != NULL && p->rightChild == cur)
		return p;

	p = Last(p->rightChild);
	return p->rightChild;
}
BinTreeNode* Parent(BinTree *t, BinTreeNode *cur)
{
	return Parent(t->root, cur);
}